class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        List<Pair<TreeNode,Integer>> q=new ArrayList<>();
        q.add(new Pair<TreeNode,Integer>(root,1));
        int ans=0;
        while(!q.isEmpty()){
            List<Pair<TreeNode,Integer>> tmp= new ArrayList<>();
            ans=Math.max(q.get(q.size()-1).getValue()-q.get(0).getValue()+1,ans);
            for(Pair<TreeNode,Integer> x:q){
                TreeNode node = x.getKey();
                int index=x.getValue();
                if(node.left!=null){
                    tmp.add(new Pair<TreeNode,Integer>(node.left,index*2));
                }
                if(node.right!=null){
                    tmp.add(new Pair<TreeNode,Integer>(node.right,index*2+1));
                }
            }
            q=tmp;
        }
        return ans;
    }
}